package algs4.ds;

import java.util.Iterator;
import java.util.NoSuchElementException;

public class ArrayQueue<E> extends Queue<E>
{
    /* Inner Class */
    private class QueueIterator implements Iterator<E>
    {
        private int cur = head;
        private int cnt = size;

        public boolean hasNext() { return cnt > 0;                                                }
        public E       next()    { E e = ary[cur]; cur = (cur + 1) % ary.length; cnt--; return e; }
    }

    /* Fields */
    private E[] ary;
    private int head;
    private int tail;
    private int size;

    /* Constructors */
    public ArrayQueue() { ary = (E[]) new Object[4]; head = tail = size = 0; }

    /* Instance Methods */
    public boolean     isEmpty()  { return size == 0;          }
    public int         size()     { return size;               }
    public Iterator<E> iterator() { return new QueueIterator(); }

    public void enqueue(E e) {
        // if queue is full, then resize the capacity
        if (size == ary.length) resize(2 * size);

        // udpate
        ary[tail] = e;
        tail = (tail + 1) % ary.length;
        size++;

        // System.out.println("enqueue: " + e);
    }

    public E dequeue() throws NoSuchElementException {
        // if queue is empty, then throws exception
        if (isEmpty()) throw new NoSuchElementException("Queue underflow");

        // retrieve element
        E e = ary[head];

        // avoid loitering
        ary[head] = null;

        // udpate
        head = (head + 1) % ary.length;
        size--;

        // if ueage rate is less than a quator, then shrink the capacity
        if (size > 1 && size == ary.length / 4) resize(2 * size);

        // System.out.println("dequeue: " + e);

        return e;
    }

    public E peek() throws NoSuchElementException {
        // if queue is empty, then throws exception
        if (isEmpty()) throw new NoSuchElementException("Queue underflow");

        return ary[head];
    }

    private void resize(int cap) {
        assert cap >= size;

        E[] dst = (E[]) new Object[cap];

        // copy from ary to dst
        int i, j;
        for (i = head, j = 0; j < size; i = (i + 1) % ary.length, j++)
            dst[j] = ary[i];

        // udpate
        ary  = dst;
        head = 0;
        tail = j;
    }

    /* Main Test */
    public static void main(String[] args) {
        Queue<Integer> queue = new ArrayQueue<>();

        for (int i = 1; i < 100; i++) {
            if (i % 3 == 0) queue.dequeue();
            else            queue.enqueue(i);
        }

        for (int i : queue)
            System.out.print(i + " ");
        System.out.println();
        System.out.println("size = " + queue.size());
    }
}
